package medium;

import java.util.Arrays;

/**
 * @author cmqzyd0700@163.com
 * @version 1.0
 * @since 2021/9/5 9:19
 */
public class No31_下一个排列 {
    public static void main(String[] args) {
        Solution31 solution31 = new Solution31();
        int[] nums = new int[]{4,6,3,2,1};
        solution31.nextPermutation(nums);
        System.out.println(nums);
    }
}

class Solution31 {
    public void nextPermutation(int[] nums) {
        fan(nums);
        int base = 0;
        int green = base;
        while (green < nums.length && nums[green] >= nums[base]) {
            base = green;
            green++;
        }
        if (green == nums.length) {
            return;
        }
        
        //从0-green-1(含) 寻找最接近于nums[green]的数
        for (int i = 0; i < green; i++) {
            if (nums[i] > nums[green]) {
                //i跟geeen位置交换
                int tmp = nums[i];
                nums[i] = nums[green];
                nums[green] = tmp;
                break;
            }
        }
        //对抓取的数组排序
        for (int i = 0; i <= (green - 1 - 0) / 2; i++) {
            //对应关系
            int tmp = nums[i];
            nums[i] = nums[green - 1 - i];
            nums[green - 1 - i] = tmp;
        }

        fan(nums);
    }

    //给nums数组进行反转
    public void fan(int[] nums) {
        int length = nums.length;
        for (int i = 0; i <= (length - 1) / 2; i++) {
            //01234 -> (04),(13) (2)
            //0123 -> (03), (12) ->???
            //对应关系
            //交换
            int tmp = nums[i];
            nums[i] = nums[length - 1 - i];
            nums[length - 1 - i] = tmp;
        }
    }
}



    //public void nextPermutation(int[] nums) {
    //    //4312 -> 4321 ...
    //    //4321 -> ??? -> 1234
    //    //数组抓取并排序,再补回 -> 强行硬写!!
    //    int green = nums.length - 1;
    //    //获取一直升序排列之后最尾的位置 <-----
    //    //获取基准比较
    //    int base = nums[green];
    //    //升序循环,注意边界越界
    //    while (green >= 0 && nums[green] >= base) {
    //        base = nums[green];
    //        green--; // -1
    //    }
    //
    //    if (green < 0) {
    //        Arrays.sort(nums);
    //        
    //        return;
    //    }
    //    
    //    //获取子数组用于比较
    //    int[] bijiao = new int[nums.length - (green + 1)];
    //    //bijiao进行赋值
    //    for (int i = 0; i < bijiao.length; i++) {
    //        bijiao[i] = nums[green + 1 + i];
    //    }
    //    //排序
    //    Arrays.sort(bijiao);
    //    
    //    //获取交换元素
    //    for (int i = 0; i < bijiao.length; i++) {
    //        if (bijiao[i] > nums[green]) {
    //            //交换位置
    //            base = bijiao[i];
    //            bijiao[i] = nums[green];
    //            nums[green] = base;
    //            break;
    //        }
    //    }
    //    
    //    //怼回去!!!!
    //    for (int i = 0; i < bijiao.length; i++) {
    //        nums[green + 1 + i] = bijiao[i]; 
    //    }
    //}




